#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution01 {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        // int cnta = 0, cntc = 0, cnto = 0, cntr = 0, cntk = 0;
        // for (auto ch : croakOfFrogs) {
        //     if (ch == 'c') {
        //         if (cntk > 0) cntk--;
        //         cntc++;
        //     } else if (cntc != 0 && ch == 'r') {
        //         cntc--;
        //         cntr++;
        //     } else if (cntr != 0 && ch == 'o') {
        //         cntr--;
        //         cnto++;
        //     } else if (cnto != 0 && ch == 'a') {
        //         cnta++;
        //         cnto--;
        //     } else if (cnta != 0 && ch == 'k') {
        //         cnta--;
        //         cntk++;
        //     } else {
        //         return -1;
        //     }
        // }
        // if (cnta + cntc + cnto + cntr > 0) return -1;
        // return cntk;
        string s = "croak";
        int n = s.size();
        vector<int> hash(n);
        unordered_map<char, int> index;
        for (int i = 0; i < n; i++)
            index[s[i]] = i;
        for (auto ch : croakOfFrogs) {
            if (ch == 'c') {
                if (hash[n - 1] != 0) hash[n - 1]--;
                hash[0]++;
            } else {
                // 先获取下标
                int i = index[ch];
                if (hash[i - 1] == 0) return -1;
                hash[i]++;
                hash[i - 1]--;
            }
        }
        for (int i = 0; i < n - 1; i++) 
            if (hash[i]) return -1;
        return hash[n - 1];
    }
};

class Solution02 {
public:
    void sortColors(vector<int>& nums) {
        // int left = 0, right = nums.size() - 1, i = 1;
        // while (left < right && nums[left] == 0)
        //     left++;
        // while (right >= 0 && nums[right] == 2)
        //     right--;
        // i = left + 1;
        // while (i <= right && left < right) {
        //     if (nums[i] == 0) {
        //         swap(nums[i], nums[left]);
        //         left++;
        //         if (nums[i] == 1)
        //             i++;
        //         if (nums[i] == 2) right--;
        //     } else if (nums[i] == 2) {
        //         swap(nums[i], nums[right]);
        //         right--;
        //         if (nums[i] == 1)
        //             i++;
        //         if (nums[i] == 0) left++;
        //     } else {
        //         i++;
        //     }
        // }
        int left = -1, i = 0, right = nums.size();
        while (i < right) {
            if (nums[i] == 0) {
                left++;
                swap(nums[left], nums[i]);
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                right--;
                swap(nums[right], nums[i]);
            }
        }
    }
};

class Solution03 {
public:
    // int getKey(int left, int right) {
    //     left = left + 1, right = right - 1;
    //     return left + (right - left) / 2;
    // }

    // pair<int, int> partition(vector<int>& nums, int left, int right) {
    //     int i = left;
    //     left--, right++;
    //     int key = left + (right - left) / 2;
    //     key = nums[key];
        
    //     while (i < right) {
    //         if (nums[i] < key) swap(nums[++left], nums[i++]);
    //         else if (nums[i] == key) i++;
    //         else swap(nums[--right], nums[i]);
    //     }
    //     // 需要返回最左边和最右边
    //     return make_pair(left, right);
    // }

    // void QS(vector<int>& nums, int left, int right) {

    //     if (left >= right) return;
    //     pair<int, int> index = partition(nums, left, right);

    //     QS(nums, left, index.first);
    //     QS(nums, index.second, right);
    // }

    void QS(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int key = l + (r - l) / 2;
        key = nums[key];
        int i = l, left = l - 1, right = r + 1;
        while (i < right) {
            if (nums[i] < key) swap(nums[++left], nums[i++]);
            else if (nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }
        QS(nums, l, left);
        QS(nums, right, r);
    }

    vector<int> sortArray(vector<int>& nums) {
        QS(nums, 0, nums.size() - 1);
        return nums;
    }
};

int main() {


    return 0;
}